/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package fr.univnantes.alma.arbres;

import java.util.Iterator;
import java.util.LinkedList;
import fr.univnantes.alma.arbres.exceptions.PereRacineException;
import fr.univnantes.alma.arbres.exceptions.PlaceIndisponibleException;

/**
 *
 * @author clotildemassot
 */
public class ArbreLA<T> implements Arbre<T>, Iterable<Noeud<T>> {

    private NoeudLA<T> racine;
    private int etiquetteCourante = 0;

    /*********** CONSTRUCTEUR ***********/
    /**
     * Constructeur par défaut (avec racine ayant une étiquette à 0)
     */
    public ArbreLA() {
        this.racine = new NoeudLA<T>(etiquetteCourante, null, 1);
        ++this.etiquetteCourante;
    }

    /*********** OPERATIONS ***********/
    /**
     * Cette fonction ajoute un fils en dernière position
     * @param  : Noeud auquel ajouter le fils
     * @return étiquette du fils nouvellement créé
     */
    public Noeud<T> ajoutFils(Noeud<T> pere) {

        NoeudLA<T> n = (NoeudLA<T>) pere;
        int position = 1;

        if (!n.getFils().isEmpty()) // Si le Noeud père a déjà des enfants
        {
            position = (n.getFils().getLast().getPosition()) + 1;
        }

        NoeudLA<T> noeud_tmp = new NoeudLA<T>(this.etiquetteCourante, n, position);
        n.getFils().add(noeud_tmp);

        ++this.etiquetteCourante;
        return noeud_tmp.autoCast();
    }


    public Noeud<T>ajoutFils(Noeud<T> pere, T valeur) throws PlaceIndisponibleException, NullPointerException {
        if(valeur == null){
            return this.ajoutFils(pere);
        } else {
            Noeud<T> tmp = this.ajoutFils(pere);
            tmp.setValeur(valeur);
            return tmp;
        }
    }

    
    /**
     * Cette fonction ajoute un fils à la position demandée
     * @param n : Noeud père auquel ajouter le nouveau Fils
     * @param pos : position où ajouter le nouveau Fils
     * @return l'étiquette du fils nouvellement créé
     * @throws PlacePriseException Si jamais la position est déjà prise
     */
    public Noeud<T> ajoutFilsEnPos(Noeud<T> pere, int pos) throws PlaceIndisponibleException {
        NoeudLA<T> n = (NoeudLA<T>) pere; // Père
        NoeudLA<T> noeud_tmp = new NoeudLA<T>(this.etiquetteCourante, n, pos); // Fils


        if (!this.positionAutorisee(pos)) {
            throw new PlaceIndisponibleException("On ne peut ajouter un fils en position" + pos);
        }
        if (this.getFilsByPos(n, pos) != null) {
            throw new PlaceIndisponibleException("Position deja occupee !");
        } else {
            LinkedList<NoeudLA<T>> fratrie = n.getFils();
            if (fratrie.isEmpty()) // Si pas de frères
            {
                fratrie.add(noeud_tmp);
            } else {
                if (pos<fratrie.getFirst().getPosition()) {
                    //Si on doit le positionner avant le premier fils
                    fratrie.addFirst(noeud_tmp);
                }
                else { //Si entre le premier fils et la fin
                int i = fratrie.getFirst().getPosition();    // position
                int j = fratrie.indexOf(fratrie.getFirst()); // index
                while (j < fratrie.size() && i < pos ) { // Recherche de l'index où rajouter le nouveau fils
                    i = fratrie.get(j).getPosition();
                    ++j;
                }
                if (j == fratrie.size()) {
                    fratrie.add(noeud_tmp);
                } // Ajout en fin
                else {
                    n.getFils().add(j, noeud_tmp);
                } // Ajout à l'index j
                }
            }
            ++this.etiquetteCourante;
        }
        return noeud_tmp;
    }


    public Noeud<T> ajoutFilsEnPos(Noeud<T> pere, int pos, T valeur) throws PlaceIndisponibleException, NullPointerException {
        if(valeur == null){
            return this.ajoutFilsEnPos(pere,pos);
        } else {
            Noeud<T> tmp = this.ajoutFilsEnPos(pere,pos);
            tmp.setValeur(valeur);
            return tmp;
        }
    }
    
    /**
     * Cette fonction permet de récupérer la racine d'un arbre
     * @return le Noeud racine de l'arbre
     */
    public Noeud<T> getRacine() {
        return this.racine.autoCast();
    }

    /**
     * Cette fonction recherche un Noeud à partir de l'étiquette
     * @param etiquette : étiquette du Noeud recherché
     * @return le Noeud trouvé, ou null si pas trouvé.
     */
    public Noeud<T> getNoeudByEtiquette(int etiquette) {
        NoeudLA<T> noeud_tmp = this.racine;
        if (noeud_tmp.getEtiquette() != etiquette) {
            noeud_tmp = RechercheNoeudByEtiq(etiquette, noeud_tmp.getFils());
        }
        return noeud_tmp.autoCast();
    }

    /**
     * Fonction récursive pour parcourir tout l'abre à la recherche d'un Noeud à partir de son étiquette
     * @param etiquette : étiquette du Noeud recherché
     * @param fratrie : liste de noeuds frères
     * @return le Noeud trouvé, ou null si pas trouvé.
     */
    private NoeudLA<T> RechercheNoeudByEtiq(int etiquette, LinkedList<NoeudLA<T>> fratrie) {
        int i = 1;
        boolean trouve = false;
        NoeudLA<T> noeud_tmp = null;
        while (i <= fratrie.size() || trouve == false) // Tant que la liste n'est pas finie, ou tant que Noeud pas trouvé
        {
            if (fratrie.get(i).getEtiquette() == etiquette) { // Si c'est le bon Noeud
                noeud_tmp = fratrie.get(i);
                trouve = true;
            } else { // Si ce n'est pas le bon Noeud
                if (!fratrie.get(i).getFils().isEmpty()) // Si ce Noeud a des fils... On refait la fonction pour la liste de ses fils
                {
                    noeud_tmp = RechercheNoeudByEtiq(etiquette, fratrie.get(i).getFils());
                }
                if (noeud_tmp == null) // Si le Noeud temporaire n'est toujours pas le bon...
                {
                    i++;
                } // Alors on continue sur le frère suivant.
                else {
                    trouve = true;
                }  // Sinon on sort du TantQue : Noeud trouvé !
                }
        }
        if (trouve == false) {
            noeud_tmp = null;
        }
        return noeud_tmp;
    }

    /**
     * Cette fonction recherche un Noeud à partir de sa position dans sa fratrie
     * Si position non trouvée, elle renvoie null
     * @param n : Noeud père
     * @param pos : position du fils recherché
     * @return le Noeud fils recherché
     */
    public Noeud<T> getFilsByPos(Noeud<T> pere, int pos) {
        if(pere == null) throw new NullPointerException("Un noeud null n'a pas de position");
        NoeudLA<T> n = (NoeudLA<T>) pere;
        LinkedList<NoeudLA<T>> fratrie = n.getFils();
        Iterator<NoeudLA<T>> it = fratrie.iterator();

        while(it.hasNext()){
            NoeudLA<T> noeud_tmp = it.next();
            if (noeud_tmp.getPosition() == pos) {
                return noeud_tmp;
            }
        }
        return null;
    }

    /**
     * Cette fonction renvoie la position du Noeud dans sa fratrie
     * @param n : Noeud
     * @return la position du Noeud
     */
    public int getPosition(Noeud<T> pere) {
        if(pere == null) throw new NullPointerException("Un noeud null n'a pas de position");
        NoeudLA<T> noeud_tmp = (NoeudLA<T>) pere;
        return noeud_tmp.getPosition();
    }

    /**
     * Cette fonction renvoie le frère suivant d'un Noeud
     * @param n : Noeud dont on cherche le frère suivant
     * @return le frère suivant
     */
    public Noeud<T> getNextFrere(Noeud<T> n) {
        if (n == null) {
            throw new NullPointerException("Un noeud null n'a pas de frère");
        }

        NoeudLA<T> noeud_tmp = (NoeudLA<T>) n;

        //si c'est la racine, pas de frère
        if(this.isRacine(noeud_tmp)) return null;
        
        LinkedList<NoeudLA<T>> fratrie = noeud_tmp.getPere().getFils();

        if (noeud_tmp.equals(fratrie.getLast())) // Si il est le dernier de sa fratrie
        {
            return null;
        } else {
            int j = fratrie.indexOf(noeud_tmp); //index du Noeud
            return fratrie.get(j + 1).autoCast(); //Récupérer index+1
        }
    }

    /**
     * Cette fonction permet de récupérer le frère précédent d'un Noeud
     * @param n : Noeud dont on veut le précédent
     * @return le frère précédent
     */
    public Noeud<T> getPreviousFrere(Noeud<T> n) {
        if (n == null) {
            throw new NullPointerException("Un noeud null n'a pas de frère");
        }

        NoeudLA<T> noeud_tmp = (NoeudLA<T>) n;

        //si c'est la racine, pas de frère
        if(this.isRacine(noeud_tmp)) return null;

        LinkedList<NoeudLA<T>> fratrie = noeud_tmp.getPere().getFils(); // Liste frères

        if (noeud_tmp.equals(fratrie.getFirst())) // Si il est le premier de sa fratrie
        {
            return null;
        } else {
            int j = fratrie.indexOf(noeud_tmp); //index du Noeud
            return fratrie.get(j - 1).autoCast(); // Récupérer index-1
            }
    }

    /**
     * Cette fonction permet de récupérer le père d'un Noeud
     * @param n : Noeud dont on veut trouver le père
     * @return le Noeud père du Noeud n
     * @throws PereRacineException si on demande le père de la racine
     */
    public Noeud<T> getPere(Noeud<T> fils) throws PereRacineException {
        NoeudLA<T> noeud_tmp = (NoeudLA<T>) fils;
        if (this.isRacine(noeud_tmp)) {
            throw new PereRacineException("La racine n'a pas de père !");
        } else {
            return noeud_tmp.getPere().autoCast();
        }
    }

    public Boolean hasNextFrere(Noeud<T> noeud) throws NullPointerException {
        return (this.getNextFrere(noeud) != null);
    }

    public Boolean hasPreviousFrere(Noeud<T> noeud) throws NullPointerException {
        return (this.getPreviousFrere(noeud) != null);
    }



    public Noeud<T> getFirstFils(Noeud<T> noeud) throws NullPointerException {
        NoeudLA<T> tmp = (noeud != null)? (NoeudLA<T>) noeud:null;
        if (tmp == null) throw new NullPointerException("Un noeud null n'a pas de fils");

        LinkedList<NoeudLA<T>> fratrie = tmp.getFils();

        if(fratrie.isEmpty()) {
            return null;
        } else {
            return fratrie.getFirst();
        }
    }

    public Boolean hasFils(Noeud<T> noeud) throws NullPointerException {
        if(noeud == null) return false;
        return (this.getFirstFils(noeud) != null);
    }


    /*********** SUPPRESSION ***********/
  
    /**
     * Supprime la liste des fils d'un Noeud
     * @param noeud dont il faut supprimer les fils
     * @throws NullPointerException
     */
    public void deleteFils(Noeud<T> noeud) throws NullPointerException {
        NoeudLA<T> pere = (NoeudLA<T>) noeud;

        /* Vérifications */
        if(noeud == null) throw new  NullPointerException();
        if(noeud.getEtiquette() > this.etiquetteCourante || noeud.getEtiquette() < 0) throw new NullPointerException("Le noeud n'appartient pas à l'arbre.");

        /* Suppression ! */
        pere.setListeFils(null); 
        // System.gc(); 
    }

    /**
     * Supprime un noeud
     * @param noeud à supprimer
     * @throws NullPointerException
     */
    public void deleteNoeud(Noeud<T> noeud) throws NullPointerException {
        //Le supprimer dans la liste des fils de son père
        /* Vérifications */
        if(noeud == null) throw new  NullPointerException();
        if(noeud.getEtiquette() > this.etiquetteCourante || noeud.getEtiquette() < 0) throw new NullPointerException("Le noeud n'appartient pas à l'arbre.");

        NoeudLA<T> fils = (NoeudLA<T>) noeud;
        fils.getPere().getFils().remove(fils);
    }

    /*********** AFFICHAGE ***********/
    
    /**
     * Affichage par listes d'adjacence (noeud et liste de ses fils)
     */
    public void affichageListAdj() {
        affichListAdj_rec(this.racine);
    }

    private void affichListAdj_rec(NoeudLA<T> n) {
        System.out.print(n.toString() + " a pour fils : ");
        n.affichageFils();
        if (!n.getFils().isEmpty()) {
            for (int i = 0; i < n.getFils().size(); i++) {
                affichListAdj_rec(n.getFils().get(i));
            }
        }
    }

    /**
     * Affichage par liste de noeuds/arcs
     */
    public void affichageNoeudArc() {
        System.out.print("Liste des noeuds : ");
        printNoeuds(this.racine);
        System.out.println("");
        System.out.print("Liste des arcs : ");
        printArcs(this.racine);
        System.out.println("");
    }

    private void printNoeuds(NoeudLA<T> n) {
        System.out.print(n.toString() + ", ");
        if (!n.getFils().isEmpty()) {
            for (int i = 0; i < n.getFils().size(); i++) {
                printNoeuds(n.getFils().get(i));
            }
        }
    }

    private void printArcs(NoeudLA<T> n) {
        if (!n.getFils().isEmpty()) {
            for (int i = 0; i < n.getFils().size(); i++) {
                System.out.print("(" + n.getEtiquette() + "," + n.getFils().get(i).getEtiquette() + ") , ");
                printArcs(n.getFils().get(i));
            }
        }
    }

    /*********** PLUS ***********/
    /**
     * Vérifie si la position est supérieure à 0
     * @param pos : position à tester
     * @return vrai si c'est >0
     */
    private Boolean positionAutorisee(int pos) {
        return pos > 0;
    }

    /**
     * Cette fonction teste si un Noeud est la racine de l'arbre
     * @param noeud : Noeud à teser
     * @return vrai si c'est la racine, faux sinon !
     */
    public Boolean isRacine(Noeud<T> noeud) {
        return (noeud.equals(this.racine));
    }

    /************** ITERATOR *****************/
    /**
     * 
     * @return iterator en BFS sur l'arbre.
     */
    public Iterator<Noeud<T>> iterator() {
        return new ArbreLAIteratorBFS<T>(this.racine);
    }

    public Iterator<Noeud<T>> iteratorBFS() {
        return new ArbreLAIteratorBFS<T>(this.racine);
    }

    public Iterator<Noeud<T>> iteratorDFS() {
        return new ArbreLAIteratorDFS<T>(this.racine);
    }

    public Iterator<Noeud<T>> iterator(ArbreIteratorType typeIt) {

        switch(typeIt){
            case DFS:
                return this.iteratorDFS();
            case BFS:
                return this.iteratorBFS();
            default:
                return this.iterator();
        }
    }

}
